package lee.study.BinaryTree.BinaryTreeTest;

class Node {//定义一个类，结点
    //属性
    public int val;//值域
    public Node left;//左子树
    public Node right;//右子树

    @Override
    public String toString() {//重写Object的toString方法
        return "Node{" +
                "val=" + val +
                '}';
    }

    //构造方法
    public Node(int val) {//构造方法
        this.val = val;


    }
}

public class BinaryTree {
    public Node buildTree() {
        Node A = new Node(1);
        Node B = new Node(3);
        Node C = new Node(5);
        Node D = new Node(7);
        Node E = new Node(9);
        Node F = new Node(11);
        Node G = new Node(13);
        Node H = new Node(15);
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }

    ////1.用递归实现三种遍历方式
    void preOrderTraversal(Node root) {//前序遍历，根左右
        if (root == null) {
            return;
        }
        System.out.println(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    void inOrderTraversal(Node root) {//中序遍历，左根右
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.println(root.val + " ");
        inOrderTraversal(root.right);
    }

    void postOrderTraversal(Node root) {//后序遍历，左右根
        if (root == null) {
            return;
        }
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.val + " ");
    }

    ///2.分别采用子问题思路和遍历思路求结点个数和叶子结点个数

    ///2.1求结点个数
    static int size = 0;

    void getSize1(Node root) {//遍历思路
        if (root == null) {
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    int getSize2(Node root) {//子问题思路
        if (root == null) {
            return 0;
        }
        return getSize2(root.left) + getSize2(root.right) + 1;
    }

    ///2.2求叶子结点个数
    static int leafSize = 0;

    void getLeafSize1(Node root) {//遍历思路
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        } else {
            getLeafSize1(root.left);
            getLeafSize1(root.right);
        }
    }

    int getLeafSize2(Node root) {//子问题思路
        if (root == null) {
            return 0;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);//左子树的叶子和右子树的叶子
    }

    // 3子问题思路-求第 k 层结点个数
    int getKlevelSize(Node root, int k) {
        if (root == null || k < 1) {//节点为空
            return 0;
        }
        if (k == 1) {//节点为1
            return 1;
        }
        return getKlevelSize(root.left, k - 1) + getKlevelSize(root.right, k - 1);
    }

    //// 查找 val 所在结点，没有找到返回 null
    // 按照 根 -> 左子树 -> 右子树的顺序进行查找
    // 一旦找到，立即返回，不需要继续在其他位置查找
    Node find(Node root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        Node ret = find(root.left, val);
        if (ret != null) {
            return ret;
        }
        ret = find(root.right, val);
        {
            if (ret != null) {
                return ret;
            }
        }
        return null;
    }

    //判断两棵树是否相等
    //1.都为空，相等
    //2.都不为空，两棵树的左树结点相等且两棵树的右树结点也相等
    public boolean isSameTree(Node t, Node p) {
        if (t == null && p == null) {//都为空
            return true;
        }
        if (t != null && p != null && t.val == p.val) {//t，p的值相等且都不为空
            return isSameTree(t.left, p.left) && isSameTree(t.right, t.right);//比较两棵树的左树和右树
        } else
            return false;
    }

    //判断一棵树是否是另一棵树的子树
    //思路：判断一棵树是否是另一颗树的子树，只需判断
    //1.两树相等
    //2.一棵树是另一颗树的左树或右树
    public boolean isSubTree(Node t, Node p) {
        if (t == null) {
            return false;
        }
        return isSameTree(t, p) || isSubTree(t.left, p) || isSubTree(t.right, p);
    }

    //一棵树的最大深度
    //思路：求出二叉树的左树深度和右树深度进行比较，最大的再加1即为最大深度
    int MaxLen(Node root) {
        if (root == null) {
            return 0;
        }
        int L = MaxLen(root.left);
        int R = MaxLen(root.right);
        return Math.max(L, R) + 1;
    }

    //平衡二叉树
    //思路:要么是完全二叉树，要么左子树深度和右子树深度差值的绝对值不超过1

    private class Return {//定义这个类来接收返回值，因为可能是两树相等(boolean)，也可能是差值不超过1(int)
        boolean tag;
        int depth;

        public Return(int depth, boolean tag) {
            this.depth = depth;
            this.tag = tag;
        }

        public boolean isBanlanced(Node root) {
            return isB(root).tag;
        }

        public Return isB(Node root) {//判断左树右树是否相等或高度差小于1
            if (root == null) {
                return new Return(0, true);
            }
            Return l = isB(root.left);
            Return r = isB(root.right);
            if (!l.tag || !r.tag) {
                return new Return(0, false);
            }
            if (Math.abs(l.depth - r.depth) > 1) {
                return new Return(0, false);
            }
            return new Return(Math.max(l.depth, r.depth) + 1, true);
        }
    }

    //对称二叉树
    //左树的左结点等于右树的右节点，左树的右节点等于右树的左结点
    public boolean isSymmetric(Node root){
        if (root==null){
            return true;
        }
        return isS(root.left,root.right);//根结点的左树与右树是否相等
    }

    public boolean isS(Node left,Node right){//左树与右树是否相等
        if (left==null&&right==null){
            return true;
        }
        if (left==null||right==null||left.val!=right.val){
            //左树为空或者右树为空或者两边值不等，返回false
            return false;
        }
        return isS(left.left,right.right)&&isS(left.right,right.left);
        //左树的左树与右树的右树是否相等，左树的右树与右树的左树是否相等
    }
}

